#include "GreedyFillGroupAlgorithm.h"
#include "Helpers.h"

using std::set;
using std::vector;

/*****************************************************************************/
// GreedyFillGroupAlgorithm
// Algorithm for filling an independent group (while keeping it independent).
// Input: Graph G=(V,E); independent Group S to be filled; 
// integer m: the required size of S (m<0 == no limitation)
// Output: The graph G & the group S after filling S.
// The algorithm can run on pairs of vertices (VertexSet).
//
/*****************************************************************************/

//-----------------------------------------------------------------------------
// Public
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// FillSingles method: The method that does the actual filling of a group, for 
// a single vertex.
// Parameters: 
// graph - the graph data structure. Notice that this parameter is 
// also an output parameter as the graph changes when we fill a group.
// group - the group to be filled. May be empty.
// size - the required size of group. If there is no reauired size, then some negative number.
// Output:
// The new group after filling. The gaph is also changed.
// Note: This method may throw an std::bad_alloc exception due to memory allocation memory
// when initiating a copy of the vertex directory.
//-----------------------------------------------------------------------------
Group& GreedyFillGroupAlgorithm::FillSingles(Graph& graph  /* also output parameter */, Group& group, VertexDirectory* directory, int size)
{
	Logger::LogMessage("Running fill singles on group "+group.PrintName());
	// create a VertexDirectory copy and use it in this run (so we don't influance the state of the graph)
	VertexDirectory* dir;
	if (directory == NULL)
	{	// use static vertex directory to create the copy
		dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
	}
	else
	{	// use the procided vertex directory to create the copy
		dir = new VertexDirectory(directory->GetWorkingCopyVertices());
	}
	// all operations are done on a copy of the graph, since we remove neighbours that should appear
	// in the graph when the algorithm finishes running
	Graph* tempGraph = graph.CloneFromDirectory(dir);
	if (tempGraph == NULL)	//memory allocation failed
	{
		delete dir;
		Logger::LogMessage("ERROR: Unable to create graph in GreedyFillGroupAlgorithm::FillSingles. Algorithm didn't run.");
		throw new GraphColoringException("ERROR: Unable to create graph in GreedyFillGroupAlgorithm::FillSingles. Algorithm didn't run.");
	}
	// all operations are done on a copy of the group	
	Group* filledGroup;
	try
	{
		filledGroup = new Group(group, dir);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		delete tempGraph;
		delete dir;
		Logger::LogMessage("ERROR: Unable to create group in GreedyFillGroupAlgorithm::FillSingles. Algorithm didn't run.");
		throw new GraphColoringException("ERROR: Unable to create group in GreedyFillGroupAlgorithm::FillSingles. Algorithm didn't run.");
	}
	
	if (filledGroup->Size() != 0)
	{
		RemoveNeighboursFromGraph(*tempGraph,*filledGroup);
	}
	Vertex* vertex = tempGraph->GetMinimalRankedVertex(filledGroup);
	while (vertex != NULL)
	{  
		// if we've reached target size - return
		if ((size != Algorithms::_NO_SIZE_LIMITATION) && (filledGroup->Size() >= size))
		{
			// update the graph & the group
			Algorithms::UpdateGraphAndGroupFromCopies(graph, group, *filledGroup);
			// free allocated memory
			delete tempGraph;
			delete filledGroup;
			delete dir;
			return group;
		}

		
		std::stringstream stream;
		stream<<"Inserting vertex "<< vertex->PrintName() <<" to new group, size will be " << filledGroup->Size()+1;
		Debug::PrintDebugMsg(stream.str());
		stream.str("");

		// vertex is a legal vertex to add to the group
		filledGroup->InsertNewVertex(vertex);
		RemoveVertexNeighboursFromGraph(*tempGraph, vertex);
		vertex = tempGraph->GetMinimalRankedVertex(filledGroup);
	}
	// no more vertices in the graph that are legal for the group
	// update the graph & the group
	Algorithms::UpdateGraphAndGroupFromCopies(graph, group, *filledGroup);
	// free allocated memory
	delete tempGraph;
	delete filledGroup;
	delete dir;
	return group;
}

//-----------------------------------------------------------------------------
// FillCouples method: The method that does the actual filling of a group, for 
// couples of vertices.
// Parameters: 
// graph - the graph data structure. Notice that this parameter is 
// also an output parameter as the graph changes when we fill a group.
// group - the group to be filled. May be empty.
// size - the required size of group. If there is no reauired size, then some negative number.
// couplesNum: number of couples to check before choosing a couple with the lowest
// rank.
// Output:
// The new group after filling. The gaph is also changed.
// Note: This method may throw an std::bad_alloc exception due to memory allocation memory
// when initiating a copy of the vertex directory.
//-----------------------------------------------------------------------------
Group& GreedyFillGroupAlgorithm::FillCouples(Graph& graph  /* also output parameter */, Group& group,VertexDirectory* directory, int size)
{
	Logger::LogMessage("Running fill couples on group "+group.PrintName());
	// create a VertexDirectory copy and use it in this run (so we don't influance the state of the graph)
	VertexDirectory* dir;
	if (directory == NULL)
	{	// use static vertex directory to create the copy
		dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
	}
	else
	{	// use the procided vertex directory to create the copy
		dir = new VertexDirectory(directory->GetWorkingCopyVertices());
	}
	
	// all operations are done on a copy of the graph, since we remove neighbours that should appear
	// in the graph when the algorithm finishes running
	Graph* tempGraph = graph.CloneFromDirectory(dir);
	if (tempGraph == NULL)	//memory allocation failed
	{
		delete dir;
		Logger::LogMessage("ERROR: Unable to create graph in GreedyFillGroupAlgorithm::FillCouples. Algorithm didn't run.");
		throw new GraphColoringException("ERROR: Unable to create graph in GreedyFillGroupAlgorithm::FillCouples. Algorithm didn't run.");
	}

	// all operations are done on a copy of the group	
	Group* filledGroup;
	try
	{
		filledGroup = new Group(group, dir);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		delete tempGraph;
		delete dir;
		Logger::LogMessage("ERROR: Unable to create group in GreedyFillGroupAlgorithm::FillCouples. Algorithm didn't run.");
		throw new GraphColoringException("ERROR: Unable to create group in GreedyFillGroupAlgorithm::FillCouples. Algorithm didn't run.");
	}
	
	if (filledGroup->Size() != 0)
	{
		RemoveNeighboursFromGraph(*tempGraph,*filledGroup);
	}
	VertexSet* vertices = tempGraph->GetMinimalRankedVertexCouple(filledGroup);
	if (vertices == NULL)
	{
		group.Clone(*filledGroup);
		// free allocated memory
		delete tempGraph;
		delete filledGroup;
		delete dir;
		return group;
	}
	//while there are still couples of vertices to add to the graph
	while (vertices != NULL && vertices->Size() == 2)
	{  
		// if we've reached target size - return 
		// (since we will add 2 vertices, we make sure that the size limitation will
		// allow adding both of them)
		if ((size != Algorithms::_NO_SIZE_LIMITATION) && (filledGroup->Size() +2 > size))
		{
			// update the graph & the group
			graph.RemoveGroupVerticesFromGraph(filledGroup);
			group.Clone(*filledGroup);
			// free allocated memory
			delete tempGraph;
			delete filledGroup;
			delete dir;
			return group;
		}

		string msg = "Inserting vertices ";
		msg.append(vertices->PrintName());
		msg.append(" to new group, size will be ");
		char size[10];
		_itoa_s(filledGroup->Size()+2,size,10);
		msg.append(size);
		Debug::PrintDebugMsg(msg);

		// vertices is a legal vertex couple to add to the group
		filledGroup->InsertNewVertexCouple(vertices);
		RemoveVertexNeighboursFromGraph(*tempGraph, vertices);
		vertices = tempGraph->GetMinimalRankedVertexCouple(filledGroup);
	}
	// no more vertices in the graph that are legal for the group
	// update the graph & the group
	graph.RemoveGroupVerticesFromGraph(filledGroup);
	group.Clone(*filledGroup);

	// free allocated memory
	delete tempGraph;
	delete filledGroup;		
	delete dir;
	return group;
}

//-----------------------------------------------------------------------------
// Private
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// RemoveNeighboursFromGraph
// Removes all the vertices in the graph that have neighbours in the group, thus
// leaving in the graph only vertices that are legal to add to the graph.
//-----------------------------------------------------------------------------
void GreedyFillGroupAlgorithm::RemoveNeighboursFromGraph(Graph &graph, Group &group)
{
	list<Vertex*>::iterator it;
	for (it=group.Iterator(); group.End(it) == false; it++)
	{
		RemoveVertexNeighboursFromGraph(graph, *it);
	}
    return;

}

//-----------------------------------------------------------------------------
// RemoveVertexNeighboursFromGraph
// Removes all the vertices in the graph that are neighbours of vertex.
//-----------------------------------------------------------------------------
void GreedyFillGroupAlgorithm::RemoveVertexNeighboursFromGraph(Graph &graph, Vertex *vertex)
{
	set<vector<bool> > neighbours = vertex->GetNeighboursInGraph();
	set<vector<bool> >::iterator it;
	for (it=neighbours.begin(); it!=neighbours.end(); it++)
	{
		Vertex* v;
		if (graph.GetVertexDirectory() != NULL)
		{	// get the vertex from the backup directory
			v = graph.GetVertexDirectory()->GetWorkingCopyVertex(*it);
		}
		else
		{	// get the vertex from the static vertex directory
			v = VertexDirectory::GetStaticCopyVertex(*it);
		}
		if (graph.IsVertexInGraph(v))
		{
			graph.RemoveVertexByName(v);		
		}
	}
    return;
}

//-----------------------------------------------------------------------------
// RemoveVertexCoupleNeighboursFromGraph
// Removes all the vertices in the graph that are neighbours of at least one of
// the vertices in the couple
//-----------------------------------------------------------------------------
void GreedyFillGroupAlgorithm::RemoveVertexNeighboursFromGraph(Graph &graph, VertexSet* vertices)
{
	RemoveVertexNeighboursFromGraph(graph, vertices->Vertex1());
	RemoveVertexNeighboursFromGraph(graph, vertices->Vertex2());
}


